import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * Dijkstra
 */
public class Dijkstra {

    public static HashMap<Integer, Integer> shortestDistanceSparse(int[][] graph, int start) {
        HashMap<Integer, Integer> dist = new HashMap<>();
        for (int i = 0; i < graph.length; i++) {
            dist.put(i, Integer.MAX_VALUE);
        }
        dist.put(start, 0);

        Comparator<int[]> nodeSorter = Comparator.comparing(x -> x[0]);
        PriorityQueue<int[]> heap = new PriorityQueue<>(nodeSorter);

        heap.add(new int[] { 0, start });
        while (!heap.isEmpty()) {
            int[] pair = heap.poll();
            int distance = pair[0];
            int cur_node = pair[1];
            if (distance > dist.get(cur_node))
                continue;

            int[] weights = graph[cur_node];
            for (int i = 0; i < weights.length; i++) {
                int dist_neighbor = dist.get(cur_node) + weights[i];
                if (dist_neighbor < dist.get(i)) {
                    dist.put(i, dist_neighbor);
                    heap.add(new int[] { dist_neighbor, i });
                }
            }
        }
        return dist;
    }

    /**
     * 每次从未求出最短路径的点集中，取出最短路径的点，放到结果中
     * 再从该点中出发，刷新未求出最短路径的点集中的距离
     * 
     * @param graph
     * @param start
     * @return
     */
    public static int[] shortestDistance(int[][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];    // 最终的最短距离
        Arrays.fill(dist, -1);      // -1表示没求出来
        dist[start] = 0;

        // 未求出最短路径的点
        int[] notFound = Arrays.copyOf(graph[start], n);
        notFound[start] = -1;       // -1表示已经求出来，或dist==-1时的无穷大

        for (int i = 1; i < n; i++) {

            // 未求出最短路径的点中找到最短路径的点
            int min = Integer.MAX_VALUE;
            int minIndex = 0;
            for (int j = 0; j < n; j++) {
                if (notFound[j] > 0 && notFound[j] < min) {
                    min = notFound[j];
                    minIndex = j;
                }
            }
            // 该点求出结果
            dist[minIndex] = min;
            notFound[minIndex] = -1;

            for (int j = 0; j < n; j++) {
                // 更新minI和j有路，且j还没求出最终距离的j点
                if (graph[minIndex][j] > 0 && dist[j] == -1) { 
                    int newDistance = dist[minIndex] + graph[minIndex][j];
                    if (newDistance < notFound[j] || notFound[j] == -1) {   //小于j或无穷大
                        notFound[j] = newDistance;
                    }
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {

        int[][] graph = new int[][] {
                { 0, 2, -1, 6 }, 
                { 2, 0, 3, 2 }, 
                { -1, 3, 0, 2 }, 
                { 6, 2, 2, 0 } };
        int[] dijkstra = shortestDistance(graph, 0);
        for (int i : dijkstra) {
            System.out.println(i);
        }
    }
}